package cn.datastruct.five;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

import static cn.datastruct.five.InsertSort.insertSort;

public class ShellSort {
    /**
     * 思路：
     *      1.shell排序基于选择排序
     *      2.间隔gap = length / 2, 并且每次 / 2，直到gap为1/2时停止循环
     *      3.开始进行选择排序，i起点值为gap,排序间隔为gap,用j保存当前位置，temp保存当前数值
     *      4.如果j - gap >= 0 && temp < arr[j  gap] 进行交换，arr[j - p]的值保持不变，j -= gap
     *      5.退出while后将arr[j]赋值为temp
     *      @param arr 需要进行shell排序的数组
     */
    public static void shellSort(int[] arr) {
        //循环
        int length = arr.length;
        for(int gap = length / 2; gap > 0; gap /= 2){//当gap为1的时候停止
            for(int i = gap; i < length; i++){//逐一增加，知道length
                int j = i;
                int temp = arr[j];
                while (j - gap > 0 && temp < arr[j - gap]){//
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
//         for(int j = i - gap; j >= 0; j -= gap){//逐一遍历
//                    while(j >= 0 && arr[j] > arr[j + gap]){
//
//                    }
//                    if(arr[j] > arr[j + gap]){//从小到大排序，小的放前面
//                        arr[j] = arr[j] ^ arr[j + gap];
//                        arr[j + gap] = arr[j] ^ arr[j + gap];
//                        arr[j] = arr[j] ^ arr[j + gap];
//                    }
//                }

            }
        }
//        for (int j = length / 2; j > 0; j /= 2)
//            for (int gap = j; gap < length; gap += 1) {//5代表组数
//                for (int i = gap - j; i >= 0; i -= j) {//表示遍历前5个数
//                    if (arr[i] > arr[i + j]) {//相隔为5个单位交换位置
//                        arr[i] = arr[i] ^ arr[i + j];
//                        arr[i + j] = arr[i] ^ arr[i + j];
//                        arr[i] = arr[i] ^ arr[i + j];
//                    }
//                }
//            }
        System.out.println(Arrays.toString(arr));
//        for (int gap = 5; gap < length; gap += 1) {//5代表组数
//            for (int i = gap - 5; i >= 0; i -= 5) {//表示遍历前5个数
//                if (arr[i] > arr[i + 5]) {//相隔为5个单位交换位置
//                    arr[i] = arr[i] ^ arr[i + 5];
//                    arr[i + 5] = arr[i] ^ arr[i + 5];
//                    arr[i] = arr[i] ^ arr[i + 5];
//                }
//            }
//        }
//        System.out.println("第一轮排序结果：" + Arrays.toString(arr));
//        //第二轮排序，分为10/2=5/2=2组
//        for (int gap = 2; gap < length; gap += 1) {//5代表组数
//            for (int i = gap - 2; i >= 0; i -= 2) {//表示遍历前5个数
//                if (arr[i] > arr[i + 2]) {//相隔为5个单位交换位置
//                    arr[i] = arr[i] ^ arr[i + 2];
//                    arr[i + 2] = arr[i] ^ arr[i + 2];
//                    arr[i] = arr[i] ^ arr[i + 2];
//                }
//            }
//        }
//        System.out.println("第二轮排序结果：" + Arrays.toString(arr));
//        //第三轮排序，分为10/2=5/2=2/2=1组
//        for (int gap = 1; gap < length; gap += 1) {//5代表组数
//            for (int i = gap - 1; i >= 0; i -= 1) {//表示遍历前5个数
//                if (arr[i] > arr[i + 1]) {//相隔为5个单位交换位置
//                    arr[i] = arr[i] ^ arr[i + 1];
//                    arr[i + 1] = arr[i] ^ arr[i + 1];
//                    arr[i] = arr[i] ^ arr[i +1];
//                }
//            }
//        }
//        System.out.println("第三轮排序结果：" + Arrays.toString(arr));


    }

    public static void main(String[] args) {
        int[] arr = {9, 2, 3, 8, 6, 7, 4, 1, 0, 5};
        shellSort(arr);
//        int[] arr = new int[10];
//        for (int i = 0; i < 10; i++) {
//            arr[i] = (int) (Math.random() * 10);
//        }
//
//        Date data1 = new Date();
//        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
//        String date1Str = simpleDateFormat.format(data1);
//        System.out.println("排序前时间" + date1Str);
//        shellSort(arr);
//        Date data2 = new Date();
//        String date2Str = simpleDateFormat.format(data2);
//        System.out.println("排序后时间" + date2Str);


    }
}
